비트마스크(BitMask) 알고리즘

이진수를 사용하는 컴퓨터의 연산 방식을 이용해, 정수의 이진수 표현을 자료 구조로 사용하는 기법

비트가 1이면 "켜져 있다"고 하며, 0이면 "꺼져 있다"고 한다

장점

수행 시간 단축(bit 연산이므로 O(1))
간결한 코드
적은 메모리 사용량

비트 연산자

AND 연산

a와 b가 모두 켜져 있는 경우에만 c를 켠다

c = a & b

OR 연산

a와 b 중 하나라도 켜져있다면 c를 켠다

c a | b

XOR 연산

배타적 OR 연산. a와 b 중 하나만 켜져 있다면 c를 켠다

c = a ^ b

NOT 연산

비트를 반전한다

c = ~a

시프트(shift) 연산

a의 비트를 왼쪽 또는 오른쪽으로 원하는 만큼 움직인다. 움직이고 나서 빈자리는 0으로 채워진다

13(1101) -> 13 >> 1 -> 6(0110)

c = a << 1

주의점

비트 연산자는 비교 연산자보다 우선 순위가 낮기 때문에,
괄호를 씌워 연산해야 한다

6 & 4 == 4 라고 하면 4 == 4가 먼저 계산된 후, 6 & 1이 계산된다